#include <stdio.h>
#include <stdlib.h>

struct node_st
{
	int coef;
	int exp;
	struct node_st *next;

};
/* 创建并插入*/
struct node_st *poly_create(int a[][2],int n)
{
	struct node_st *me,*cur,*new_node;
	me = malloc(sizeof(*me));
	if(me == NULL)
		return NULL;

	me->next = NULL;/* 头结点创建完毕*/

	cur = me;

	int i;
	for(i=0;i<n;i++)
	{
		new_node = malloc(sizeof(*new_node));
		if(new_node == NULL)
			return NULL;/* 处理解释：一旦有一个创建失败 就GG*/
		/* order_insert更加安全*/
		new_node->coef = a[i][0];
		new_node->exp = a[i][1];
		
		cur->next = new_node;
		cur = new_node;
	}

	return me;
}
/* 创建并按序插入*/
struct node_st *poly_create_order_insert(int a[][2],int n)
{
	struct node_st *me;
	me = malloc(sizeof(*me));
	if(me == NULL)
		return NULL;

	me->next = NULL;/* 头结点*/

	/*order_insert*/
	struct node_st *me_temp = me;
	int i;
	for(i = 0;i<n;i++)
	{
		while(me_temp->next && a[i][1] > me_temp->next->exp)
		{
			me_temp = me_temp->next;
		}/*me_temp 为前驱*/
		struct node_st *temp2 = NULL;
		temp2 =malloc(sizeof(*temp2));
		if (temp2 == NULL)
			return NULL;
		temp2->coef = a[i][0];
		temp2->exp = a[i][1];
	
		temp2->next = me_temp->next;
		me_temp->next = temp2;
	printf("%d %d   ",a[i][0],a[i][1]);/* 小心数组越界*/
	
	}
	printf("\ntest_end\n");
	return me;
}

void poly_show(struct node_st *me)
{
	struct node_st *cur;
	for (cur = me->next;cur;cur = cur->next)
	{
		printf("%d ^%d |",cur->coef,cur->exp);	
	}
	printf("\n");
}
// 已经exp从小到大排好了
int poly_union(struct node_st *p1,struct node_st *p2)
{
	struct node_st *p,*q,*r;
	
	p = p1->next;
	q = p2->next;/*已跳过头结点*/
	
	/* 对比 向目标链表上插入*/
	r = p1;

	while(p && q)
	{
		if(p->exp < q->exp)/*链接(插入目标链表)*/
		{
			r->next = p;
			r = p;
			p = p->next;
		}
		else if(p->exp > q->exp)
		{
			r->next = q;
			r = q;
			q = q->next;	
		}
		else/* p ->exp == q-> exp*/
		{
			p->coef +=q ->coef;
			if ( p ->coef)
			{
				r->next = p;
				r = p;
			}
			p=p->next;
			q=q->next;
		}
	}

	if (p == NULL)
		r->next = q;
	else
		r->next = p;
	return 0;
}


/* 多项式合并*/
int main()
{
	int a[][2] = {{5,0},{2,1},{8,8},{3,16}};
	int b[][2] = {{6,1},{16,6},{-8,8}};
	struct node_st *p1,*p2;

	p1 = poly_create(a,4);
	p2 = poly_create(b,3);
	if(!p1 || !p2)
	{
		exit(1);
	}	
	poly_show(p1);
	poly_show(p2);
#if 0
	/*poly_create_order_insert test!*/
	struct node_st *p3;
	int c[][2] = {{1,2},{5,6},{2,4},{3,3}};
	p3 = poly_create_order_insert(c,4);
	poly_show(p3);
#endif
	poly_union(p1,p2);

	poly_show(p1);
	exit(0);
}
